# encoding=utf-8
import itertools

def mostrarGrafo(graph, problem):
	'''Esta função exibe em terminal o caminho percorrido e os nós expandidos
	A partir de um grafo ou árvore no formato [[A,[B,C],[D,[E,F]]] onde cada
	lista interna é um nó e uma lista de nós expandidos'''

	msg = "Partindo de: " + problem.initial + '\n'
	msg = "-> Explorados: "
	if len(graph) != 1:
		for i in graph[0][1]:
			msg = msg + i.strip('0123456789') + ' '
		msg = msg + '\n'
		for noh in range(1, len(graph)):
			if len((graph[noh])[1]) != 0:
				msg = msg + "Expandindo:" + (graph[noh])[0].strip('0123456789') + ' '
				msg = msg + "-> Explorados: "
				for i in(graph[noh])[1]:
					msg = msg + i.strip('0123456789') + ' '
				msg = msg + '\n'
	else:
		msg = 'Explorados: Nenhum'
	return msg

def custo(problem, solution, mapa):
	'''Esta função calcula o custo total do início até o objetivo dado um
	problema, a solução (uma lista de nós) e o mapa (dicionário) no qual foi
	feita a procura'''

	custo = 0.0

	if len(solution) != 0:
		custo = mapa.get(problem.initial, solution[0])
		for i in range(len(solution) - 1):
			custo += mapa.get(solution[i], solution[i + 1])
	return custo

def draw_graph(graph, mapa, solution, problem):
	'''Função que transforma o grafo ou árvore de saída em um formato exigido
	pela biblioteca pygraph por meio da função tkGraphView'''

	node_edge_old_style = []
	lista_expandidos = []

	for no in graph:
		lista_expandidos.append(no[0])

	lista_explorados = []
	for no in graph:
		lista_explorados.extend(no[1])

	for no in lista_explorados:
		if no not in lista_expandidos:
			graph.append([no, []])
	for no in graph:
		tmpnode = {}
		# [A,[B,C,D]] (formato do nosso nó)
		tmpnode['node'] = no[0]
		tmpnode['shape'] = 'oval'
		tmpnode['features'] = ''
		tmpnode['edges'] = [i for i in no[1]]
		tmplista = []
		for nohDeChegada in no[1]:
			tmplista.append(str(mapa.get(no[0].strip('0123456789'), nohDeChegada.strip('0123456789'))))
		tmpnode['edgenames'] = tmplista
		if no[0] not in solution and no[0] != problem.initial:
			tmpnode['color'] = 'green'
		else:
			tmpnode['color'] = 'cyan'
		node_edge_old_style.append(tmpnode)
	node_edge_old_style = [k for k, v in itertools.groupby(sorted(node_edge_old_style))]
	return node_edge_old_style

def encontra_string_em_elemento(lista, procura):
	'''Esta função é usada para localizar um string em uma lista do tipo usada
	para gerar a lista da árvore, onde é permitido repetir nós e portanto para
	ser gerada com sucesso na biblioteca que exibe graficamente um nó que já exista
	na árvore precisa ser renomeado, e pra isso precisamos localizar o último nó adicionado
	e incluir um número após ele para ser considerado um novo nó pelo pygraph
	Ex: se o nó que repete é o A este nó deve ser renomeado para A1'''

	achou = False
	for i in range(len(lista) - 1, -1, -1):
		if lista[i].find(procura) != -1:
			achou = True
			break

	if achou:
		return i
	else:
		return None

